Consulta de Guías Docentes



Academic Year/course: 2023/24

453 - Degree in Mathematics

27005 - Graphs and Combinatorics


Syllabus Information

Academic year:
2023/24
Subject:
27005 - Graphs and Combinatorics
Faculty / School:
100 - Facultad de Ciencias
Degree:
453 - Degree in Mathematics
ECTS:
6.0
Year:
1
Semester:
Second semester
Subject type:
Compulsory
Module:
---

1. General information

When solving different scientific problems, some combinatorial and graph theory questions arise, and it is important to know how to recognize and solve them. The main objective of this course is then to present basic techniques in the combinatorial analysis, as well as methods and algorithms to solve basic problems in graph theory.

The approaches and objectives of this module are aligned with the Sustainable Development Goals (SDGs) of the United Nations 2030 Agenda; the learning activities could contribute to some extent to the achievement of the goals 4 (quality education), 5 (gender equality), 8 (decent work and economic growth), and 10 (reducing inequality).

2. Learning results

  • Solve elementary problems of ordering and enumeration.
  • Know and manage the concept of generating function and the recurrence formula.
  • Use generating functions to obtain formulas for enumeration problems.
  • Know the basics of graph theory and its most elementary applications.
  • Apply the basic algorithms of graph theory to solve problems.

3. Syllabus

Section I

  1. Enumerative combinatorics: permutations and combinations.
  2. Binomial coefficients.
  3. Recurrence relations. Some applications.
  4. The inclusion-exclusion principle. Applications.

Section II

  1. Generating functions.
  2. Rational generating functions.

Section III

  1. Graphs: definitions and notation.
  2. Traversing a graph. Algorithms BFS and DFS.
  3. Applications of graph traversal: connected components, strong components, bases.
  4. The number of trees and paths of a graph.

Section IV

  1. Weighted graphs. Algorithms for the minimum spanning tree problem.
  2. The shortest path problem. Dijkstra's algorithm.
  3. PERT-CPM algorithms for scheduling a set of project activities.

Section V

  1. Maximum flow in a network.
  2. The Ford-Fulkerson method for calculating a maximum flow.
  3. Menger’s theorems on connectivity of graphs.
  4. Maximum matching in bipartite graphs. Hall's theorem.
  5. Some NP-Hard problems on graphs.

4. Academic activities

Master classes: 30 hours.
Problem solving: 30 hours.
Study: 84 hours.
Assessment tests: 6 hours.

5. Assessment system

There will be one 2-hour midterm exam, only on combinatorics topics. Each student will get a mark, P1, in the range 0 to 10.

In the 4-hour final exam, there will be two parts: One with questions on combinatorics and the other one with questions about graph theory. The marks obtained in each part, E1 and E2, will be also in the range 0 to 10.

The final grade, C, will be either C = 0.5*(E1+E2) if P1<4, or C=0.5*(Max(P1,E1)+E2) if P1≥4.

The grade required to pass the course is 5 or greater.


Curso Académico: 2023/24

453 - Graduado en Matemáticas

27005 - Grafos y combinatoria


Información del Plan Docente

Año académico:
2023/24
Asignatura:
27005 - Grafos y combinatoria
Centro académico:
100 - Facultad de Ciencias
Titulación:
453 - Graduado en Matemáticas
Créditos:
6.0
Curso:
1
Periodo de impartición:
Segundo semestre
Clase de asignatura:
Obligatoria
Materia:
---

1. Información básica de la asignatura

En la resolución de diferentes problemas científicos, aparecen de forma natural cuestiones de tipo combinatorio o de teoría de grafos, que es importante saber reconocer y saber resolver. Por ello, el objetivo fundamental de esta asignatura es presentar las técnicas básicas del análisis combinatorio, así como los métodos y algoritmos de resolución de problemas básicos sobre grafos.

Los planteamientos y objetivos de la asignatura están alineados con los Objetivos de Desarrollo Sostenible (ODS) de la Agenda 2030 de Naciones Unidas; en concreto, las actividades de aprendizaje previstas en esta asignatura contribuirán en alguna medida al logro de los objetivos 4 (educación de calidad), 5 (igualdad de género), 8 (trabajo decente y crecimiento económico) y 10 (reducción de las desigualdades).

2. Resultados de aprendizaje

  • Resolver problemas elementales de ordenación y enumeración.
  • Conocer y manejar el concepto de función generatriz y el de fórmula de recurrencia.
  • Utilizar las funciones generatrices para obtener fórmulas para problemas de enumeración.
  • Conocer el lenguaje y las aplicaciones más elementales de la teoría de grafos.
  • Aplicar los algoritmos básicos de teoría de grafos para resolver problemas.

3. Programa de la asignatura

TEMA I

  1. Combinatoria elemental. Permutaciones  y combinaciones.
  2. Coeficientes binomiales.
  3. Recurrencias. Aplicaciones.
  4. El principio de inclusión-exclusión. Aplicaciones.

TEMA II

  1. Funciones generatrices.
  2. Funciones generatrices racionales.

TEMA III

  1. Definición y notaciones para grafos.
  2. Problema de recorrido de un grafo. Algoritmos BFS y DFS.
  3. Aplicaciones. Cálculo de componentes y bases.
  4. Número de árboles y caminos de un grafo.

TEMA IV

  1. Grafos con costos. Algoritmos para calcular el árbol mínimo.
  2. Caminos más cortos: Algoritmo de Dijkstra.
  3. Técnicas PERT-CPM de planificación de proyectos.

TEMA V

  1. Flujo en redes. Conceptos básicos.
  2. Algoritmo de Ford- Fulkerson para cálculo de máximo flujo.
  3. Teoremas de conectividad de Menger.
  4. Matching en grafos bipartitos. Teorema de Hall.
  5. Algunos problemas NP-duros sobre grafos.

4. Actividades académicas

Clases magistrales: 30 horas.
Resolución de problemas y casos: 30 horas.
Estudio: 84 horas.
Pruebas de evaluación: 6 horas.

5. Sistema de evaluación

Al terminar la primera parte de la asignatura (temas de combinatoria), se realizará una prueba parcial, donde se examinará al alumno sobre esos contenidos de combinatoria y se le calificará con una nota, P1, entre 0 y 10.

En la fecha oficial de una convocatoria se realizará un examen con dos partes diferenciadas, una con preguntas de combinatoria, la otra con cuestiones de teoría de grafos. Las calificaciones obtenidas en cada una de esas partes (E1 y E2) serán también sobre 10 puntos.

La calificación, C, de la asignatura, obtenida en esa convocatoria oficial será:

  • Si P1 es menor que 4, C = 0.5*(E1+E2).
  • Si P1 es mayor o igual que 4, C = 0.5*(Max(P1,E1)+E2).

Habrán superado la asignatura en esa convocatoria quienes hayan obtenido una calificación C mayor o igual a 5.